Ce que nous allons construire 🎯
- La structure de données : Une File de priorité (FP).
- C’est un type abstrait de données, comme une liste ou une file, mais avec une particularité.
- Chaque élément possède une « priorité » (une clé).
- Lorsque vous effectuez une opération « pop », vous obtenez toujoursl'élément ayant la plus haute priorité.
- Les opérations :
- 1.
push(k) - 2.
peek() - 3.
pop()
- 1.
- L’implémentation :Nous utiliserons un tas binaire max.
- Pourquoi un tas ? C’est efficace ! Un tas nous offre :
push: O(log N)pop: O(log N)peek: O(1)
Qu'est-ce qu'un tas binaire max ?
Un arbre binaire avec deux règles simples :
1. Propriété de forme
C’est un arbre binaire complet. Tous les niveaux sont remplis, sauf éventuellement le dernier, qui est rempli de gauche à droite. Il n’y a aucun trou.
Cliquez sur une feuille pour la supprimer
2. Propriété du tas max
La clé d’un parent est supérieure ou égale àcelle de ses enfants. Cela garantit que l’élément le plus grandest toujours à la racine.
Stockage de l’arbre 💾
Puisque l’arbre est complet, nous pouvons le stocker parfaitement dans un tableau simple.
Calcul des indices (base 0)
Pour un nœud à l’indice i :
- Parent
(i - 1) // 2 - Fils gauche
2 * i + 1 - Fils droit
2 * i + 2
Conseil :Mémorisez ces formules ! Elles sont la clé pour naviguer dans l’« arbre » contenu dans votre tableau.